Java Concurrent - CopyOnWriteArrayList

发表于 | 分类于

Overview

copy-on-write容器在计算机世界常常出现, 如果不了解可以参考Java中的Copy-On-Write容器. CopyOnWriteArrayList特性简要概括如下:

  • 内存中有可能存在两个数组, 写时占用更多存储空间.
  • 写操作之间仍然是互斥的, 同一时刻仍然只有一个线程可以进行写操作.
  • 写操作进行时会先复制出一个副本出去(假设为B), 读操作仍然读取原来的数据(假设为数组A). 即在数组A上就不再存在写操作, 所以读取时不需要加锁.

根据其特性, 可以发现读取操作如size,get,indexOf, 几乎和平常的列表没有任何不同.

实际应用

在尝试实现RPC框架时, 需要使用一个列表来保存注册的Provider地址. 而Provider的数量实际上不会很大, 而且服务的上下线频率实际上非常低, 远远小于读取次数. 这种场景下正好使用CopyOnWriteList, 可以保证读取效率和ArrayList一致.

一致性

CopyOnWriteArrayList的实现主要基于两个Java并发机制, 即ReentrantLock和volatile.

1
2
3
transient final ReentrantLock lock = new ReentrantLock();

private volatile transient Object[] array;

前者负责为所有的写操作加锁, 后者保证修改数组引用后的可见性. 列举简单的add方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;    // mark ->
        setArray(newElements);  // 修改array引用.
        return true;
    } finally {
        lock.unlock();
    }
}

在锁操作中, 复制当前数组, 最后修改array引用. 真 · copy-on-write而已. 而这里有一个本身特性带来问题, 即 此容器虽然最终一致, 但是确不是实时读写一致的.

假设线程A进入了写操作add, 另一个线程B同时读取.

  • 如果A线程已经执行了setArray, 那么根据volatile变量的特性, B线程当然可见.
  • 然而由于读操作无锁, 假设A线程刚刚执行到标记mark的位置, 同时B线程进行读操作, 则明显读到的还是之前的数组.

happens-before

注释

请看注释:

Memory consistency effects: As with other concurrent collections, actions in a thread prior to placing an object into a CopyOnWriteArrayList happen-before actions subsequent to the access or removal of that element from the CopyOnWriteArrayList in another thread.

翻译:

内存一致性影响: 和其他并发集合一样, 在一个线程内, 如果某个操作在插入元素到CopyOnWriteArrayList之前发生, 那么此操作happpens-before于另一个线程中CopyOnWriteArrayList读写之后发生的操作.

真绕口.. happens-before比较好理解: A操作happens-beforeB操作, 即A执行的结果对于B可见. 对于上面这句注释, 没理解的话先放下, 继续看. 这段来自 JSR133 FAQ

JSR133 FAQ

Under the new memory model, it is still true that volatile variables cannot be reordered with each other. The difference is that it is now no longer so easy to reorder normal field accesses around them. Writing to a volatile field has the same memory effect as a monitor release, and reading from a volatile field has the same memory effect as a monitor acquire. In effect, because the new memory model places stricter constraints on reordering of volatile field accesses with other field accesses, volatile or not, anything that was visible to thread A when it writes to volatile field f becomes visible to thread B when it reads f.

翻译:

在新内存模型下, 相同之处是volatile变量之间仍然不能被重排序. 而差别在于volatile变量前后的其他变量重排序不再那么简单. 对于volatile变量的写操作和monitor释放有相同的效果, 对于volatile变量的读操作也和Monitor获取有相同效果. 实际上, 由于新的内存模型对于volatile变量和其他变量(无论是否为volatile)的重排序更严格, 当线程A写入volatile变量f时, 而线程B在读取f, 那么A可见的一切对B都可见.

文中举例如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class VolatileExample {
  int x = 0;
  volatile boolean v = false;
  public void writer() {
    x = 42;
    v = true;
  }

  public void reader() {
    if (v == true) {
      //uses x - guaranteed to see 42.
    }
  }

}

A线程调用writer(), B调用reader(). 由于v为volatile, 所以v之前的非volatile变量写操作x = 42对于线程B中的x读取一定可见.

set(int index, E element)

在CopyOnWriteArrayList中的一段看似较为奇怪的代码, 就是来保证刚刚的内存一致性的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public E set(int index, E element) {
       final ReentrantLock lock = this.lock;
       lock.lock();
       try {
           Object[] elements = getArray();
           E oldValue = get(elements, index);

           if (oldValue != element) {
               int len = elements.length;
               Object[] newElements = Arrays.copyOf(elements, len);
               newElements[index] = element;
               setArray(newElements);
           } else {
               // Not quite a no-op; ensures volatile write semantics
               setArray(elements);  ---> 看这里
           }
           return oldValue;
       } finally {
           lock.unlock();
       }
   }

即其中标注”看这里”的位置, 它的作用和VolatileExample中的v相同, 借用volatile变量来保证一致性. 引用stackoverflow上面的一段示例, 实际上和VolatileExample非常相似:

1
2
3
4
5
6
7
8
9
10
11
12
13
// initial conditions
int nonVolatileField = 0;
CopyOnWriteArrayList<String> list = /* a single String */

// Thread 1
nonVolatileField = 1;                 // (1)
list.set(0, "x");                     // (2)

// Thread 2
String s = list.get(0);               // (3)
if (s == "x") {
    int localVar = nonVolatileField;  // (4)
}

类比之下, 应该比较容易理解了. 虽然nonVolatileField非volatile, 但是操作(1)happens-before操作(4). 综上, CopyOnWriteArrayList通过volatile实现一种内存一致性影响.

See Also